#include <iostream>
#include <string>
#include <vector>

using namespace std;
// 这是一个dfs的写法

string split_token = ",";
string null_token = "null";

/**
 * 这样写的效率可能不高，但本人能力有限，先这么写了
 * @param st 需要分割的字符串
 * @param token 根据什么来划分
 * @return 元素为字符串分割后各部分的向量，不包含token
*/
vector<string> split(const string &st, const string &token) {
    vector<string> res;

    int length_of_token = token.size();
    size_t pos = 0;
    for (size_t edpos = st.find(token, pos);
        edpos != string::npos;
        pos = edpos + length_of_token, edpos = st.find(token, pos)
        ) {
        res.push_back(st.substr(pos, edpos - pos));
    }
    if (pos < st.size()) res.push_back(st.substr(pos));
    return res;
}

// 对于 Node 的 定义
typedef struct Node {
    int val;
    Node *left;
    Node *right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
}*PNode;

Node *_Deserialize(const vector<string> &nodes, size_t &cnt) {
    if (cnt >= nodes.size() || nodes[cnt] == null_token) { cnt++; return nullptr; }
    PNode root = new Node(stoi(nodes[cnt++])); // string to int
    root->left = _Deserialize(nodes, cnt);
    root->right = _Deserialize(nodes, cnt);
    return root;
}

Node *Deserialize(string seqs) {
    //write ur code here.
    vector<string> nodes = split(seqs, split_token);
    size_t cnt = 0;
    return _Deserialize(nodes, cnt);
}

string Serialize(Node *root) {
    //write ur code here.
    if (root == nullptr) return null_token;
    return to_string(root->val) + split_token + Serialize(root->left) + split_token + Serialize(root->right);
}

// #include "tools.h"

void PreOrderprintTree(Node *root) {
    if (root == nullptr) { cout << null_token << split_token;return; }
    cout << root->val << split_token;
    PreOrderprintTree(root->left);
    PreOrderprintTree(root->right);
}

int main(int argc, char const *argv[]) {
    /* code */
    Node *root = new Node(31);
    root->left = new Node(2);
    root->left->left = new Node(4);
    root->left->left->right = new Node(5);
    root->right = new Node(3);
    string se = Serialize(root);
    cout << "加密后为: " << se << endl;
    Node *deroot = Deserialize(se);
    cout << "解密后为: ";
    PreOrderprintTree(deroot); cout << endl;
    return 0;
}


